/* 264. 丑数 II */
/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function (n) {
    /* dp[i]表示第i个丑数 */
    const dp = new Array(n + 1).fill(0)
    dp[1] = 1

    /* 
        获取其余丑数
        定义3个指针 p2,p3,p5 表示下一个丑数是当前指针指向的丑数乘以对应的质因数
    */
    let p2 = 1, p3 = 1, p5 = 1
    for (let i = 2; i <= n; i++) {
        const num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5
        dp[i] = Math.min(num2, num3, num5)
        if (dp[i] === num2) {
            p2++
        }
        if (dp[i] === num3) p3++
        if (dp[i] === num5) p5++
    }
    return dp[n]
};
nthUglyNumber(10)


